/**
 * [70] 爬楼梯
 *
 * @format
 * @lc app=leetcode.cn id=70 lang=javascript
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
// 通项公式
/* var climbStairs = function(n) {
    const sqrt5 = Math.sqrt(5);
    const fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return Math.round(fibn / sqrt5);
}; */
// 动态规划
var climbStairs = function (n) {
    const memo = [1, 1, 2]
    function recursion(n) {
        if (memo[n]) return memo[n]
        memo[n] = recursion(n - 1) + recursion(n - 2)
        return memo[n]
    }
    return recursion(n)
}
// @lc code=end
